class Solution {//leetcode37——解数独
private:
    bool is_Sudoku(vector<vector<char>>& board,int x,int y,int num){
        if(cols[x][num]==true||rows[y][num]==true||grids[y/3][x/3][num]==true){
            return false;
        }
        return true;
    }
    void init_sudoku(const vector<vector<char>>& board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.'){
                    int num=board[i][j]-'0';
                    cols[j][num]=rows[i][num]=grids[i/3][j/3][num]=true;
                }
            }
        }
    }
    bool dfs(vector<vector<char>>&board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]=='.'){
                    for(int num=1;num<=9;num++){
                        if(is_Sudoku(board,j,i,num))
                        {
                            board[i][j]=num+'0';
                            cols[j][num]=rows[i][num]=grids[i/3][j/3][num]=true;
                            if(dfs(board)){
                                return true;
                            }
                            board[i][j]='.';
                            cols[j][num]=rows[i][num]=grids[i/3][j/3][num]=false;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        init_sudoku(board);
        dfs(board);
    }
private:
    bool cols[9][10];
    bool rows[9][10];
    bool grids[3][3][10];
};